package code.D1219;

import java.util.Arrays;

/**
 * author： yeswater
 * create： 2023/12/22
 *
 * 最长递增子序列
 *
 */
public class T300 {
    /**
     * 状态定义：
     * dp[i] 的值代表 nums 以nums[i]结尾的最长子序列长度
     *
     * 转移方程：
     * 0 < j < i
     * 1、当 nums[i]>nums[j] nums[i] 可以接在nums[j]之后 此时最长长度为 dp[j]+1
     * 2、当 nums[i]<=nums[j] nums[i] 无法接在 nums[j]之后 此时子序列不成立 跳过
     *
     * 上述所有 当情况 1计算出的dp[j]+1 的最大值，为直到 i 的最长上升子序列长度 即dp[i]
     * 实现方式为 遍历 j 时，每轮执行 dp[i]=Math.max(dp[i], dp[j]+1)
     *
     * 初始状态：
     * dp[i]所有元素置为1 含义是每个元素至少可以单独成为子序列 此时长度为 1
     *
     * 返回值：
     * 返回dp数组最大值
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp =new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
